/**
 * @file fourprimes.cpp
 * Solves the sum of four primes problem as detailed by
 * UVA problem 10168
 *
 * @author Kyle Heck
 */

#include <cassert>
#include <bitset>
#include <math.h>
#include <sstream>
#include <iostream>

using namespace std;
#define MAX_NUM  10000000
#define MAX_BUF  9

void  comp_sieve    (bitset<MAX_NUM> &array, int max_value);
int   string_to_int (const char* s_num);
void  print_sum     (int total, bitset<MAX_NUM> &sieve);
int   next_prime    (int num, bitset<MAX_NUM> &sieve);
int   prev_prime    (int num, bitset<MAX_NUM> &sieve);

int main (int argc, char* argv[]) {
	bitset<MAX_NUM> is_prime;
	char input_buffer[MAX_BUF];
	comp_sieve(is_prime, MAX_NUM); 

	while (!cin.fail()) {
		cin.getline(input_buffer, MAX_BUF);
		if (cin.eof()) {
		    break;
		}
		int total = string_to_int(input_buffer);
		print_sum(total, is_prime);
	}

	return 0;
} 

/**
 * Computes and prints solution to problem
 * @param total The number to which we want our answer 
 *        to sum to
 * @param sieve A bitset that contains a table of primes
 *        0 = prime, 1 = composite
 */
void print_sum(int total, bitset<MAX_NUM> &sieve) {

	assert(total >= 0 && total < MAX_NUM);	

	if (total <= 7) {
		cout << "Impossible." << endl;
		return;
	}

	int x = 2;
	total = total - 4;

	if (total % 2 == 1) {
		x++;
		total--;
	}  

	for (int a = 2; a != -1 && a < total; a = next_prime(a, sieve)) {
		if (sieve[total-a] == 0){ 
			cout << a << " " << total - a << " " << x << " " << 2 << endl;
			return;
		}
	} 

	cout << "Impossible." << endl;               

}

/**
 * Given a number and a prime table return the next prime
 * @param num The number to which the next prime will be returned
 *        ie (next_prime(3, ___) = 5
 * @param sieve The table of primes.  0 = prime, 1 = composite
 * @return The closest greater prime to the number provided. If no
 *         larger primes exist, next_prime returns -1
 */
int next_prime(int num, bitset<MAX_NUM> &sieve) {
	assert(num > 0);
	while (++num < MAX_NUM) {
		if (sieve[num] == 0) {
			return num;
		}
	}

	return -1;
}
/**
 * Given a number and a prime table return the previous prime
 * @param num The number to which the prev. prime will be returned
 *        ie (next_prime(3, ___) = 2
 * @param sieve The table of primes.  0 = prime, 1 = composite
 * @return The closest lesser prime to the number provided. If no
 *         smaller primes exist, prev_prime returns -1
 */
int prev_prime(int num, bitset<MAX_NUM> &sieve) {
	assert(num > 0);
	while (--num >= 0) {
		if (sieve[num] == 0) {
			return num;
		}
	}
	return -1;

}              

/**
 * Computes a table of primes using the sieve of eratosthenes
 * @param array Empty bitset, size <= calculation bounds
 * @param max_value Upper bound on computation range
 */
void comp_sieve(bitset<MAX_NUM> &array, int max_value) {
	assert(max_value > 0 && MAX_NUM >= max_value);
	const int sqr_root = (int)ceil(sqrt(max_value)) + 1; 

	/* 0 and 1 aren't calculated, manual entry needed */
	array[0] = 1;
	array[1] = 1;

	int factor = 2;
	while (factor < sqr_root) {
		for (int cofactor = 2; cofactor * factor <= max_value; cofactor++) {
			array[factor * cofactor] = 1;
		}
		while (array[++factor] == 1);       
	}    
}

/**
 * Converts a string to an integer
 * @param s_num number in string form
 * @return number in integer form
 */
int string_to_int (const char* s_num) {
	stringstream stream(s_num);
	int i_num;
	stream >> i_num;
	assert(i_num >= 0);
	return i_num;
}

